perm filename PAPER.NEW[1,LMM] blob
sn#040760 filedate 1973-05-05 generic text, type T, neo UTF8
COMMENT ⊗ VALID 00028 PAGES
RECORD PAGE DESCRIPTION
00001 00001
00004 00002 .<<pub declarations>>
00005 00003 PART A. THE LABELLING PROBLEM.
00008 00004 SYMMETRY AND ITS RELATIONSHIP TO LABELLING
00010 00005 .<< Figure 2 >>
00013 00006 .<<TABLE I>>
00015 00007 .<< DEF EQUIVALENT >>
00017 00008 .<<Figure 3>>
00019 00009 PERMUTATIONS AND PERMUTATION GROUPS
00022 00010 .<< TABLE III >>
00025 00011 .BEGIN NOFILL GROUP
00028 00012 .BEGIN NOFILL GROUP
00029 00013 PART B. SOLUTION TO THE LABELLING PROBLEM
00031 00014 ∪A_∪Better_∪Method
00033 00015 .<<figure 6>>
00035 00016 2. Computing orbits
00038 00017 2. The reduced symmetry group.
00041 00018 .SEND FOOT ⊂
00042 00019 ∪LABEL_∪RECURSION
00044 00020 .<<figure 7>>
00045 00021 ∪ORBIT_∪RECURSION
00047 00022 In some of these cases there are more than one possibility (cases
00049 00023 Second, label {2,4,7,9} with 1 N (and 3 blanks). Note that {2,4,7,9} is no
00051 00024 FINAL TECHNIQUE.
00053 00025 For example, the cyclohexane skeleton has a group of order twelve
00056 00026 Fortunately, this technique is rarely necessary -- usually
00058 00027 C.∪SUMMARY_∪OF_∪LABELLING_∪STEPS
00061 00028 REFERENCES
00062 ENDMK
⊗;
.<<pub declarations>>
.every heading({DATE}, LABELLING OBJECTS WITH SYMMETRY,PAGE {PAGE})
.NEXT PAGE
.TURNON "↑↓[]∪"
PART A. THE LABELLING PROBLEM.
.BREAK
The problem attacked is one of finding all distinct ways to assign a
given number of labels
or colors to the parts of a symmetric object when it is also known
how many parts get each of the labels or colors.
This problem is encountered in a wide range of applications beyond
chemistry-- within many areas of graph theory and combinatorics, for
example. It has been known how to compute the number of solutions
[1], but an efficient method of actually constructing
the solutions has not previously been reported. The discussion in this
paper is restricted to the labelling of graphs with the "topological"
symmetry groups; the algorithm, however, is immediately applicable to
other types of labellings; one could, for example, generate all distinct
"permutational isomers" for a given three dimensional ring system
as defined in Ruch [2].
.BEGIN NOFILL
----------------------------------------------------------------------
| INSERT HERE |
| a long discussion with several examples - define permutational |
|isomers from Ruch, explain how the algorithm is applicable. Perhaps |
|the queen's problem might also be worthwhile. |
|anyway, need to read up Ruch and use it. |
----------------------------------------------------------------------
.END
SYMMETRY AND ITS RELATIONSHIP TO LABELLING
.BREAK
Consider the special case of the general problem: suppose all
of the labels are distinct. This means that, for example,one wishes to
number the faces of a cube with the numbers {1,2,3,4,5,6}, or the
"nodes" (atom positions in a graph) of the decalin skeleton with numbers
{1,2,3,4,5,6,7,8,9,10}. There are n! (n factorial) ways of labelling
where n is the number of parts. If the object has no symmetry
then each of these n! ways are distinct from the rest. However
for the decalin skeleton (where n! = 10! =
10x9x8x7x6x5x4x3x2x1 = 3,628,800 ways) there is some symmetry. Pick one
of the numberings as a point of
reference (Fig 2a). Some of the 10! ways are different (Fig 2b); some
of them are essentially the same (Fig 2c).
.BEGIN NOFILL GROUP
------------------------------------------------------------
Figure 1
The Decalin Skeleton
⊗ ⊗
/ \ / \
/ \ / \
⊗ ⊗ ⊗
| | |
| | |
⊗ ⊗ ⊗
\ / \ /
\ / \ /
⊗ ⊗
------------------------------------------------------------
.END
.<< Figure 2 >>
.BEGIN NOFILL GROUP
------------------------------------------------------------
Figure 2
Three of the 10! numberings of
the Decalin Skeleton.
2 4 7 1 4 2
/ \ / \ / \ / \ / \ / \
/ \ / \ / \ / \ / \ / \
1 3 5 2 8 9 5 3 1
| | | | | | | | |
| | | | | | | | |
10 8 6 3 4 5 6 8 10
\ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ /
9 7 6 10 7 9
(2a) (2b) (2c)
------------------------------------------------------------
.END
Intuitively, Figs 2a and 2c are equivalent because one could
take 2a, flip it over and get 2c. There is another way of determining
the "sameness" of such numberings which is easier in the more complicated
cases and is in general more suited to computer application:
.BREAK
Write down the respective "connection tables". (See Table I). Note
that the connection table for Fig 2c is identical to that of Fig 2a;
that of Fig 2b is different.
.<<TABLE I>>
.BEGIN VERBATIM GROUP
------------------------------------------------------------
Table I.
node|connected | node|connected | node|connected
| to | | to | | to
| |
1 2,10 | 1 8,9 | 1 2,10
2 1,3 | 2 7,3 | 2 1,3
3 2,4,8 | 3 2,6 | 3 2,4,8
4 3,5 | 4 6,8,10 | 4 3,5
5 4,6 | 5 9,10 | 5 4,6
6 5,7 | 6 3,4 | 6 5,7
7 6,8 | 7 2,8 | 7 6,8
8 3,7,9 | 8 1,4,7 | 8 3,7,9
9 8,10 | 9 1,5 | 9 8,10
10 1,9 | 10 4,5 | 10 1,9
------------------------------------------------------------
.END
.<< DEF EQUIVALENT >>
.BEGIN INDENT 6,6,6
DEFINITION: two numberings of the nodes of a graph are ∪equivalent
if the connection tables of the respective numberings are identical when
the node numbers are written in ascending order and each "connected to"
is in ascending order.
.END
This means, among other things, that properties such as valency
are preserved: If two numberings are equivalent and in the first, node
1 is trivalent then in the second, node 1 is trivalent. If there are
other properties of the nodes (already colored or labelled, for example),
then this definition can be extended to include the preserving of those
properties.
.BREAK
For example, suppose there are atom names associated with (some of)
the nodes of the graph. Then one can define equivalent numberings
to be those which not only have identical connection tables, but also
the same atom names
for the corresponding nodes. Then Fig 3a would still be equivalent
to Fig 3c but no longer to Fig 3b since, although the connection tables
of 3a and 3b are identical, node 1 in Fig 3a is labelled with an "N" while
while in 3b it is unlabelled.
.BREAK
.<<Figure 3>>
.BEGIN NOFILL GROUP
----------------------------------------------------------
Figure 3.
Partially labelled graphs reduce
the equivalencies.
2 4 9 7 4 2
/ \ / \ / \ / \ / \ / \
/ \ / \ / \ / \ / \ / \
N1 3 5N N10 8 6N N 3 1N
| | | | | | | | |
| | | | | | | | |
10 8 6 1 3 5 6 8 10
\ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ /
9 7 2 4 7 9
(3a) (3b) (3c)
----------------------------------------------------------
.END
PERMUTATIONS AND PERMUTATION GROUPS
.BREAK
Given one numbering, one can use a condensed notation
to write down others in terms of the first.
In Table II, take the 2b case. The row of numbers means that, in
sequence, the node
numbered 1 in the reference numbering 2a is now numbered 2, the node originally
numbered 2 is now numbered 10, and so on. All of these are written down with
respect to the original "reference" numbering of figure 2a.
.BEGIN NOFILL GROUP
-------------------------------------------------------------
Table II
Condensed Notation for Numberings
Figure 2a numbers: 1 2 3 4 5 6 7 8 9 10
Figure 2b numbers: 2 10 3 7 4 6 5 8 1 9
Figure 2c numbers: 5 4 3 2 1 10 9 8 7 6
-------------------------------------------------------------
.END
One can conceptualize a numbering as a transformation or as a function:
The transformation for 2c is π↓2↓c(1)=5, π↓2↓c(2)=4, π↓2↓c(3)=3, ...
π↓2↓c(10)=6. These transformations are ∪permutations: one to one mappings from
the integers {1,2,...,n} to themselves. The transformation for
the "reference" numbering is the identity i(x)=x. It can be shown that
whatever the graph, the set of transformations satisfying the "equivalency"
requirement above satisfies the property of a group. One may then say:
.BEGIN INDENT 6
The ∪symmetry ∪group of a graph is the set of all transformations which
yield identical connection tables. (If there are other properties
to be considered, one may include them as part of the connection table).
For the decalin skeleton there are 4 permutations in the group.
.END
.<< TABLE III >>
.BEGIN NOFILL GROUP
-------------------------------------------------------------------- Table III
The Symmetry Group
of the Decalin Skeleton
π↓i 1 2 3 4 5 6 7 8 9 10
π↓v 5 4 3 2 1 10 9 8 7 6
, one needs to find a row.
To find the labellings, one needs to pick one element from each row.
.BEGIN NOFILL GROUP
-------------------------------------------------------------
Figure 4
Equivalence classes, Groups, and Labellings
;.diagram here;
.GROUP SKIP 30
-------------------------------------------------------------
.END
PART B. SOLUTION TO THE LABELLING PROBLEM
.BREAK
∪A_∪Naive_∪Method
.BREAK
An obvious method to find the distinct labellings would be to
generate all n! of the possible ones, and for each one to check if
an equivalent one was previously generated. Unfortunately, this method
takes an exhorbitant amount of computation (proportional to n! squared).
Below is discussed a
method which takes an amount of time roughly proportional to the
number of solutions (i.e. the number of equivalence classes of labellings)
and requires only knowledge of the symmetry group (thus it is useful
for labelling objects using their geometric symmetry as well as the
topological symmetry defined above).
.BREAK
∪A_∪Better_∪Method
.BREAK
1. Special case: distinguish 1 node.
.BREAK
First consider the special case where there are only two types
of labels and furthermore that there is only one of one of the types.
(E.g., color one red, and the rest green, or label one N and the rest C.)
Intuitively, for the decalin skeleton, one can see that there
are three "types" of nodes, labelled with "⊗", "+" and "&" in Fig.
5, and that each distinct labelling corresponds to selecting one node
from each type. (see Fig 6.)
.BEGIN NOFILL GROUP
-------------------------------------------------------------
Figure 5
Orbits in the Decalin Skeleton
⊗ ⊗
/ \ / \
/ \ / \
+ & +
| | |
| | |
+ & +
\ / \ /
\ / \ /
⊗ ⊗
-------------------------------------------------------------
.END
9(∂%Y .<<figure 6>>
.BEGIN NOFILL GROUP
-------------------------------------------------------------
Figure 6
Three Labellings of Decalin with
1 N and 9 C's.
⊗ ⊗ N ⊗ ⊗ ⊗
/ \ / \ / \ / \ / \ / \
/ \ / \ / \ / \ / \ / \
N ⊗ ⊗ ⊗ ⊗ ⊗ ⊗ N ⊗
| | | | | | | | |
| | | | | | | | |
⊗ ⊗ ⊗ ⊗ ⊗ ⊗ ⊗ ⊗ ⊗
\ / \ / \ / \ / \ / \ /
\ / \ / \ / \ / \ / \ /
⊗ ⊗ ⊗ ⊗ ⊗ ⊗
-------------------------------------------------------------
.END
Thus there are three distinct labellings (the ten possible labellings
split into three equivalence classes).
.BREAK
2. Computing orbits
.BREAK
In general, the parts of an object with symmetry split into different
"types" (sometimes there is only one type, as in the faces of a cube, or
the nodes of the cyclohexane skeleton). To label the
parts of an object such that one is distinguished, it is necessary only
to find the "types" and then, for each type, pick one of the parts in
that type arbitrarily. Note that if the object has no symmetry each
type has exactly one part in it.
.BREAK
It is very simple to find the different types from the
table of the symmetry group: if one writes out the group, as in Table III,
with each permutation as a row, then the numbers in each column, taken as
a set, form a "type". Such "types" are called ∪orbits of the symmetry group.
The orbits of the group in Table III are: {1,5,6,10}, {2,4,7,9}, {3,8}.
.BREAK
After finding the set of orbits, one then can do this special
labelling: the number of distinct labellings is the number of orbits.
Each corresponds to selecting an element from an corresponding orbit
and labelling it. For reasons to be explained later, the first element
of each orbit should be chosen (i.e. the one with the smallest number
in the reference numbering).
.BREAK
One might note here that if one has n-1 labels and 1 "blank" it is the
same as 1 label and n-1 "blanks". This special case can be applied
here as well.
2. The reduced symmetry group.
.BREAK
Once a group has been calculated for a structure, many times one wants to
know what the group is after some labels have been attached. The group
of a labelled structure is always a ∪subset of the group of the unlabelled
structure. Thus one needs to know which permutations in the group must
be thrown out. To do this, write the "labels" associated with each node
next to the node number in the permutation table as in Table II. If in
any column, there is an element which has a different label than the label
in the "reference" numbering (identity permutation), then that row can
be discarded. That is, every permutation in the reduced symmetry group
must satisfy:
.BEGIN NOFILL
for every node i, label(π(i))=label(i).
.END
Exactly those permutations in the original group that satisfy this equation
are the ones in the reduced symmetry group of the labelled structure.
.BREAK
3. Reduction techniques
.BREAK
In the general labelling problem, there are two important techniques used to
reduce the problem. The first is called LABEL RECURSION↑* and the second
ORBIT RECURSION. The idea behind LABEL RECURSION is that one can do
one label at a time. The idea behind ORBIT RECURSION is that one can label
one orbit at a time. These reductions are discussed in detail
below.
.BREAK
.SEND FOOT ⊂
------------------------
.BREAK
.INDENT 0,6,6
* A ∪recursive technique is one which is defined in terms of itself. For
example, n! can be defined by:
.begin nofill
{ 1 if n=1
n! = {
{ n*(n-1)! otherwise
.END
.CONTINUE
The computation of 10! involves computing another factorial. It is necessary
that at each step, the problem is reduced. Here the general solution of
the labelling
problem is described in terms of less complicated labellings.
Several special
cases (analogous to the n=1 case in the definition of factorial) are
also defined.
.⊃;
∪LABEL_∪RECURSION
.BREAK
If one is given many (more than 2) kinds of labels, say n↓1 of
type 1, n↓2 of type 2, ... n↓k of type k, proceed as follows:
(1) solve the labelling problem for n↓1 of one type of label
and n↓2+n↓3+...+n↓k of another type. (Call the second type of label
"blank"). The result will be a list of partially labelled
objects (along with their reduced symmetry groups). Take each
of the results and label the "blank" parts with n↓2 labels of
one kind, n↓3 of another, ... ,n↓k of another. It can be proved
that the results will be a list of all distinct solutions to the
original problem. For example, to label the decalin skeleton with
1 label "N", 1 label "S" and 8 labels "C", one first labels with
1 "N" and 9 "blanks" obtaining the 3 results in figure 7a.
(Fig 7a1,7a2,7a3). There are now 3 new problems to label
The "blanks" if Figs 7a1-3 (under their respective reduced symmetry),
with 1 "S" and 8 "C"'s. In Figs 7a1 and 7a2, there is no symmetry
left, and so each of the "blanks" has its own orbit, thus
there are 9 distinct labellings apiece. In Fig. 7a3, there
are 5 orbits under the reduced symmetry, and thus there are 5
additional possibilities. (Fig 7b).
.BREAK
.<<figure 7>>
.BEGIN NOFILL GROUP
-------------------------------------------------------------
Figure 7
Labellings with 1 N, 1 S, and 8 C's.
⊗ ⊗
/ \ / \
N ⊗ ⊗
7a1 | | |
⊗ ⊗ ⊗
\ / \ /
⊗ ⊗
N ⊗
/ \ / \
⊗ ⊗ ⊗
7a2 | | |
⊗ ⊗ ⊗
\ / \ /
⊗ ⊗
⊗ ⊗
/ \ / \
⊗ N ⊗
7a3 | | |
⊗ ⊗ ⊗
\ / \ /
⊗ ⊗
-------------------------------------------------------------
.END
∪ORBIT_∪RECURSION
.BREAK
There are 3 cases in the 1 N, 9 C on the decalin skeleton problem.
.BEGIN NOFILL
(case 1) 1 N goes to orbit {1,5,6,10}.
(case 2) 1 N goes to orbit {2,4,7,9},
(case 3) 1 N goes to orbit {3,8}.
.END
There is only one possibility in each of these cases.
Suppose there were 3 N's. Then there would be 9 cases. (Table IV).
.BEGIN VERBATIM GROUP
------------------------------------------------------------
Table IV.
(3 N's on a decalin)
# N's going to
case orbit orbit orbit
number {1,5,6,10} {2,4,7,9} {3,8}
1 3 - -
2 2 1 -
3 2 - 1
4 1 2 -
5 1 1 1
6 1 - 2
7 - 3 -
8 - 2 1
9 - 1 2
------------------------------------------------------------
.END
In some of these cases there are more than one possibility (cases
2,3,4,5 and 8). However, every labelling fits into one of
these cases, and labellings from different cases cannot be equivalent.
.BREAK
Thus, each of these cases can be done independently, and the results
collected together. To do any one of the cases, the labellings of the
orbits can be done sequentially.
.BREAK
Take case 5. First label one of {1,5,6,10} with one N, (and the
rest "blanks"). Since {1,5,6,10} is an orbit, we can chose one
arbitrarily and get Fig 8. (The first one is chosen).
.BEGIN NOFILL GROUP
------------------------------------------------------------
Figure 8
1 N to orbit {1,5,6,10}
⊗ ⊗
/ \ / \
/ \ / \
N ⊗ ⊗
| | |
| | |
⊗ ⊗ ⊗
\ / \ /
\ / \ /
⊗ ⊗
------------------------------------------------------------
.END
Second, label {2,4,7,9} with 1 N (and 3 blanks). Note that {2,4,7,9} is no
longer an orbit under the reduced group. Stick to the original plan-- it is
just necessary to find ∪new orbits under the reduced group to label {2,4,7,9}.
Since there is no symmetry left, each of {2,4,7,9} falls into its own orbit.
The "special case" can be used directly to find the 4 solutions (Fig 9).
.BEGIN NOFILL GROUP
------------------------------------------------------------
Figure 9
Second step of case 5
N ⊗ ⊗ N
/ \ / \ / \ / \
N ⊗ ⊗ N ⊗ ⊗
9a | | | 9b | | |
⊗ ⊗ ⊗ ⊗ ⊗ ⊗
\ / \ / \ / \ /
⊗ ⊗ ⊗ ⊗
⊗ ⊗ ⊗ ⊗
/ \ / \ / \ / \
N ⊗ ⊗ N ⊗ ⊗
9c | | | 9d | | |
⊗ ⊗ ⊗ ⊗ ⊗ ⊗
\ / \ / \ / \ /
⊗ N N ⊗
------------------------------------------------------------
.END
Then, for each of these solutions, {3,8} must be labelled with 1 N
(and 1 blank). The final result is 8 possibilities for case 5, none
of which have any remaining symmetry.
.BREAK
FINAL TECHNIQUE.
.BREAK
Now the only problem to be solved is this: suppose there
are two types of labels, n↓1 of the first, and n↓2 of the second,
neither n↓1 or n↓2 are 1, and there is only one orbit. No more
simple reductions left.
The solution, however, is another trick. Pick the first node and label
it, calculating the reduced symmetry group and new orbits.
Label the rest of the nodes (under the reduced group) with n↓1-1
labels of type 1 and n↓2 labels of type 2. The result will
contain a representative of each equivalence class of labellings;
however, if n↓1>2 then there may be some duplicates (i.e., two
of the results may